[BAEKJOON] 1884. 고속도로

Posted on January 12, 2021

문제 :

봄캠프 기간 동안 고속도로의 통행료가 급격하게 올라, 참가자들이 자칫 집으로 돌아가지 못할 수도 있는 위기에 봉착했다! 통행료가 인하되기 전까지는 여기 속초에서 원쌤과 함께 계속 프로그래밍 공부를 해야 할 수도 있는 상황인 것이다! 이 모든 것은 귀가시에 사용할 교통비를, 고속도로 통행료가 오르기 전에 계산해서 들고 왔기 때문이다.

다급해진 여러분은 정해진 예산을 가지고 집으로 돌아갈 수 있을지 알아보고, 갈 수 있다면 그에 필요한 최단 이동거리를 계산하려고 한다. 이를 해결하기 위한 프로그램을 작성하라.

입력 :

첫 줄에 여러분이 준비해 둔 교통비 K가 주어진다. (0≤K≤10,000) 둘째 줄과 셋째 줄에는 각각 도시의 숫자 N과 도로의 숫자 R이 주어진다. (2≤N≤100, 1≤R≤10,000) 이후 R개의 줄에 각 도로의 정보가 주어지는데, 각 줄은 네 개의 숫자 s, d, l, t로 이루어져 있다. s는 도로의 출발 도시 번호이고, d는 도로의 도착 도시 번호이다. l은 도로의 길이이고, t는 도로의 통행료이다. (1≤s≤N, 1≤d≤N, 1≤l≤100, 0≤t≤100)

도시의 번호는 1번부터 N번까지 빠짐없이 붙어 있다. 이곳 속초는 1번 도시이고, 여러분의 집은 N번 도시에 있다. 각 도로는 일방통행로이다. 서로 다른 두 도로가 서로 같은 시작 도시와 서로 같은 도착 도시를 가질 수 있음에 유의하라.

출력 :

첫 줄에 정해진 예산 내에서 이용할 수 있는 경로 중 제일 짧은 것의 길이를 출력한다. 만약 가능한 경로가 없을 때에는 -1을 출력한다.

풀이 :

문제 접근을 잘못해서 몇 번이고 코드를 지웠다 다시 짜는 걸 반복해서 꽤나 시간이 걸린 문제였다..

문제 접근을 처음부터 잘할 수 있도록 문제를 확실하게 파악하는 연습을 할 필요가 있을 듯 하다.

처음에는 단순히 dfs로 모든 경로를 가보고 교통비가 넘지 않는 최소 경로를 찾으면 되지 않을까 너무 쉽게 생각했다. → 이 방법은 같은 노드를 지속적으로 방문하기 때문에 너무 오랜 시간이 소요되는 알고리즘 방식이다.

그래서 각 노드를 한번씩 방문하면서 최소 경로를 찾을 수 있는 다익스트라를 활용했다. 여기서 핵심적으로 파악할 부분은 기본적인 다익스트라 알고리즘에서 교통비까지 고려해주어야 한다는 것이다.

즉 해당 노드의 가장 짧은 거리로 올 수 있는 방법으로 탐색을 했더라도 그 방법보다 거리는 길지만 교통비는 작은 경우도 다시금 고려해주어야 한다.

왜냐하면 가장 짧은 거리가 교통비를 초과할 수 있기 때문이다.

따라서 나는 기존의 다익스트라에서는 해당 노드 방문 여부를 체크하는 bool 형식의 visit 배열을 두었는데 이번 코드에서는 visit 배열에 교통비를 저장해두고 만약 저장된 교통비보다 작은 교통비로 해당 노드를 방문한 경우면 탐색을 허용하도록 코드를 구현하였다.

코드 :

코드 보기/접기

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef struct Node {
    int node;
    int dist;
    int fee;
} Node;

struct compare {
    bool operator()(Node a, Node b) {
        return a.dist > b.dist;
    }
};

vector<vector<Node>> adj;
int k, n, visit[101];

int dijkstra() {
    priority_queue<Node, vector<Node>, compare> pq;
    fill_n(visit, 101, 987654321);
    pq.push(Node{1, 0, 0});

    while (!pq.empty()) {
        int curidx = pq.top().node, curfee = pq.top().fee, curdist = pq.top().dist;
        pq.pop();
        if (visit[curidx] <= curfee || curfee > k) continue;
        if (curidx == n) return curdist;
        visit[curidx] = curfee;
        int i, size = adj[curidx].size();
        for (i = 0; i < size; i++)
            pq.push(Node{adj[curidx][i].node, curdist + adj[curidx][i].dist, curfee + adj[curidx][i].fee});
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int r, s, d, l, t;
    cin >> k >> n >> r;
    adj.resize(n + 1);
    while (r--) {
        cin >> s >> d >> l >> t;
        adj[s].push_back(Node{d, l, t});
    }
    cout << dijkstra() << '\n';
    return 0;
}

Algorithm

algorithm baekjoon C++